package algorithm.dynamic_planning.leetcode;

import java.util.List;

/**
 * 三角形最小路径和
 *
 * @author yuisama
 * @date 2022/04/29 19:46
 **/
public class Num120_MinimumTotal {
    Integer[][] memo;
    // 1.记忆化搜索
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return dfs(triangle,0,0);
    }

    /**
     * 以当前第i行和第j列为起始元素向下的最短路径和
     * @param triangle
     * @param i
     * @param j
     * @return
     */
    public int dfs(List<List<Integer>> triangle,int i,int j) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        memo[i][j] = triangle.get(i).get(j) + Math.min(dfs(triangle,i + 1,j),
                dfs(triangle,i + 1,j + 1));
        return memo[i][j];
    }
//    public int minimumTotal(List<List<Integer>> triangle) {
//
//    }
}